<!DOCTYPE html>
<html lang="zh-CN" data-theme="light">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <meta name="generator" content="VuePress 2.0.0-beta.38" />
    <meta name="theme" content="VuePress Theme Hope" />
    <meta property="og:url" content="https://javaguide.cn/cs-basics/data-structure/linear-data-structure.html"><meta property="og:site_name" content="JavaGuide"><meta property="og:title" content="线性数据结构 :数组、链表、栈、队列"><meta property="og:type" content="article"><meta property="og:updated_time" content="2022-03-03T01:14:56.000Z"><meta property="og:locale" content="zh-CN"><meta property="article:tag" content="数据结构"><meta property="article:modified_time" content="2022-03-03T01:14:56.000Z"><script>var _hmt = _hmt || [];
      (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?5dd2e8c97962d57b7b8fea1737c01743";
        var s = document.getElementsByTagName("script")[0]; 
        s.parentNode.insertBefore(hm, s);
      })();</script><link rel="stylesheet" href="//at.alicdn.com/t/font_2922463_99aa80ii7cf.css"><title>线性数据结构 :数组、链表、栈、队列 | JavaGuide</title><meta name="description" content="Java学习&&面试指南">
    <style>
      :root {
        --bg-color: #fff;
      }

      html[data-theme="dark"] {
        --bg-color: #1d2025;
      }

      html,
      body {
        background-color: var(--bg-color);
      }
    </style>
    <script>
      const userMode = localStorage.getItem("vuepress-theme-hope-scheme");
      const systemDarkMode =
        window.matchMedia &&
        window.matchMedia("(prefers-color-scheme: dark)").matches;

      if (userMode === "dark" || (userMode !== "light" && systemDarkMode)) {
        document.querySelector("html").setAttribute("data-theme", "dark");
      }
    </script>
    <link rel="stylesheet" href="/assets/style.aa943f56.css">
    <link rel="modulepreload" href="/assets/app.93341f6d.js"><link rel="modulepreload" href="/assets/linear-data-structure.html.38192640.js"><link rel="modulepreload" href="/assets/linear-data-structure.html.50841415.js"><link rel="modulepreload" href="/assets/plugin-vue_export-helper.21dcd24c.js">
  </head>
  <body>
    <div id="app"><!--[--><!--[--><!--[--><span tabindex="-1"></span><a href="#main-content" class="skip-link sr-only">Skip to content</a><!--]--><div class="theme-container has-toc sidebar-open"><!--[--><header class="navbar"><button class="toggle-sidebar-button" title="Toggle Sidebar"><span class="icon"></span></button><a href="/" class="home-link"><img class="logo" src="/logo.png" alt="JavaGuide"><!----><span class="site-name hide-in-pad">JavaGuide</span><!--[--><!----><!--]--></a><nav class="nav-links" style=""><div class="nav-item hide-in-mobile"><a href="/home.html" class="nav-link" arialabel="面试指南"><i class="icon iconfont icon-java"></i>面试指南<!----></a></div><div class="nav-item hide-in-mobile"><a href="/zhuanlan/" class="nav-link" arialabel="优质专栏"><i class="icon iconfont icon-recommend"></i>优质专栏<!----></a></div><div class="nav-item hide-in-mobile"><a href="/open-source-project/" class="nav-link" arialabel="项目精选"><i class="icon iconfont icon-github"></i>项目精选<!----></a></div><div class="nav-item hide-in-mobile"><a href="/books/" class="nav-link" arialabel="书籍精选"><i class="icon iconfont icon-book"></i>书籍精选<!----></a></div><div class="nav-item hide-in-mobile"><a href="https://snailclimb.gitee.io/javaguide/#/" rel="noopener noreferrer" target="_blank" arialabel="旧版链接" class="nav-link"><i class="icon iconfont icon-java"></i>旧版链接<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="nav-item hide-in-mobile"><a href="https://javaguide.cn/feed.json" rel="noopener noreferrer" target="_blank" arialabel="RSS订阅" class="nav-link"><i class="icon iconfont icon-rss"></i>RSS订阅<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="nav-item hide-in-mobile"><a href="/about-the-author/" class="nav-link" arialabel="关于作者"><i class="icon iconfont icon-zuozhe"></i>关于作者<!----></a></div></nav><div class="nav-actions-wrapper"><!--[--><!----><!--]--><div class="nav-item"><!----></div><div class="nav-item"><a class="repo-link" href="https://github.com/Snailclimb/JavaGuide" target="_blank" rel="noopener noreferrer"><svg xmlns="http://www.w3.org/2000/svg" class="icon github-icon" viewbox="0 0 1024 1024" arialabelledby="github" style="width:1.25rem;height:1.25rem;vertical-align:middle;"><title id="github" lang="en">github icon</title><g fill="currentColor"><path d="M511.957 21.333C241.024 21.333 21.333 240.981 21.333 512c0 216.832 140.544 400.725 335.574 465.664 24.49 4.395 32.256-10.07 32.256-23.083 0-11.69.256-44.245 0-85.205-136.448 29.61-164.736-64.64-164.736-64.64-22.315-56.704-54.4-71.765-54.4-71.765-44.587-30.464 3.285-29.824 3.285-29.824 49.195 3.413 75.179 50.517 75.179 50.517 43.776 75.008 114.816 53.333 142.762 40.79 4.523-31.66 17.152-53.377 31.19-65.537-108.971-12.458-223.488-54.485-223.488-242.602 0-53.547 19.114-97.323 50.517-131.67-5.035-12.33-21.93-62.293 4.779-129.834 0 0 41.258-13.184 134.912 50.346a469.803 469.803 0 0 1 122.88-16.554c41.642.213 83.626 5.632 122.88 16.554 93.653-63.488 134.784-50.346 134.784-50.346 26.752 67.541 9.898 117.504 4.864 129.834 31.402 34.347 50.474 78.123 50.474 131.67 0 188.586-114.73 230.016-224.042 242.09 17.578 15.232 33.578 44.672 33.578 90.454v135.85c0 13.142 7.936 27.606 32.854 22.87C862.25 912.597 1002.667 728.747 1002.667 512c0-271.019-219.648-490.667-490.71-490.667z"></path></g></svg></a></div><div class="nav-item hide-in-mobile"><button id="appearance-switch"><svg xmlns="http://www.w3.org/2000/svg" class="icon auto-icon" viewbox="0 0 1024 1024" arialabelledby="auto" style="display:block;"><title id="auto" lang="en">auto icon</title><g fill="currentColor"><path d="M512 992C246.92 992 32 777.08 32 512S246.92 32 512 32s480 214.92 480 480-214.92 480-480 480zm0-840c-198.78 0-360 161.22-360 360 0 198.84 161.22 360 360 360s360-161.16 360-360c0-198.78-161.22-360-360-360zm0 660V212c165.72 0 300 134.34 300 300 0 165.72-134.28 300-300 300z"></path></g></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon dark-icon" viewbox="0 0 1024 1024" arialabelledby="dark" style="display:none;"><title id="dark" lang="en">dark icon</title><g fill="currentColor"><path d="M524.8 938.667h-4.267a439.893 439.893 0 0 1-313.173-134.4 446.293 446.293 0 0 1-11.093-597.334A432.213 432.213 0 0 1 366.933 90.027a42.667 42.667 0 0 1 45.227 9.386 42.667 42.667 0 0 1 10.24 42.667 358.4 358.4 0 0 0 82.773 375.893 361.387 361.387 0 0 0 376.747 82.774 42.667 42.667 0 0 1 54.187 55.04 433.493 433.493 0 0 1-99.84 154.88 438.613 438.613 0 0 1-311.467 128z"></path></g></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon light-icon" viewbox="0 0 1024 1024" arialabelledby="light" style="display:none;"><title id="light" lang="en">light icon</title><g fill="currentColor"><path d="M952 552h-80a40 40 0 0 1 0-80h80a40 40 0 0 1 0 80zM801.88 280.08a41 41 0 0 1-57.96-57.96l57.96-58a41.04 41.04 0 0 1 58 58l-58 57.96zM512 752a240 240 0 1 1 0-480 240 240 0 0 1 0 480zm0-560a40 40 0 0 1-40-40V72a40 40 0 0 1 80 0v80a40 40 0 0 1-40 40zm-289.88 88.08-58-57.96a41.04 41.04 0 0 1 58-58l57.96 58a41 41 0 0 1-57.96 57.96zM192 512a40 40 0 0 1-40 40H72a40 40 0 0 1 0-80h80a40 40 0 0 1 40 40zm30.12 231.92a41 41 0 0 1 57.96 57.96l-57.96 58a41.04 41.04 0 0 1-58-58l58-57.96zM512 832a40 40 0 0 1 40 40v80a40 40 0 0 1-80 0v-80a40 40 0 0 1 40-40zm289.88-88.08 58 57.96a41.04 41.04 0 0 1-58 58l-57.96-58a41 41 0 0 1 57.96-57.96z"></path></g></svg></button></div><form class="search-box" role="search"><input type="search" placeholder="搜索" autocomplete="off" spellcheck="false" value><!----></form><button class="toggle-navbar-button" aria-label="Toggle Navbar" aria-expanded="false" aria-controls="nav-screen"><span class="button-container"><span class="button-top"></span><span class="button-middle"></span><span class="button-bottom"></span></span></button><!--[--><!----><!--]--></div></header><!----><!--]--><!----><div class="toggle-sidebar-wrapper"><span class="arrow left"></span></div><aside class="sidebar"><!--[--><!----><!--]--><ul class="sidebar-links"><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-mianshi"></i><span class="title">面试准备</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-java"></i><span class="title">Java</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable active"><i class="icon iconfont icon-computer"></i><span class="title">计算机基础</span><span class="arrow down"></span></button><ul class="sidebar-links"><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-network"></i><span class="title">网络</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-caozuoxitong"></i><span class="title">操作系统</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable active"><i class="icon iconfont icon-people-network-full"></i><span class="title">数据结构</span><span class="arrow down"></span></button><ul class="sidebar-links"><li><!--[--><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html" class="router-link-active router-link-exact-active nav-link active sidebar-link sidebar-page active" arialabel="线性数据结构 :数组、链表、栈、队列"><!---->线性数据结构 :数组、链表、栈、队列<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_1-数组" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="1. 数组"><!---->1. 数组<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-链表" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="2. 链表"><!---->2. 链表<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-1-链表简介" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="2.1. 链表简介"><!---->2.1. 链表简介<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-2-链表分类" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="2.2. 链表分类"><!---->2.2. 链表分类<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-3-应用场景" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="2.3. 应用场景"><!---->2.3. 应用场景<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-4-数组-vs-链表" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="2.4. 数组 vs 链表"><!---->2.4. 数组 vs 链表<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-栈" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="3. 栈"><!---->3. 栈<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-1-栈简介" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="3.1. 栈简介"><!---->3.1. 栈简介<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-2-栈的常见应用常见应用场景" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="3.2. 栈的常见应用常见应用场景"><!---->3.2. 栈的常见应用常见应用场景<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-3-栈的实现" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="3.3. 栈的实现"><!---->3.3. 栈的实现<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-队列" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="4. 队列"><!---->4. 队列<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-1-队列简介" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="4.1. 队列简介"><!---->4.1. 队列简介<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-2-队列分类" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="4.2. 队列分类"><!---->4.2. 队列分类<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-3-常见应用场景" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="4.3. 常见应用场景"><!---->4.3. 常见应用场景<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/graph.html" class="nav-link sidebar-link sidebar-page" arialabel="图"><!---->图<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/heap.html" class="nav-link sidebar-link sidebar-page" arialabel="堆"><!---->堆<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/tree.html" class="nav-link sidebar-link sidebar-page" arialabel="树"><!---->树<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/red-black-tree.html" class="nav-link sidebar-link sidebar-page" arialabel="红黑树"><!---->红黑树<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/bloom-filter.html" class="nav-link sidebar-link sidebar-page" arialabel="布隆过滤器"><!---->布隆过滤器<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-suanfaku"></i><span class="title">算法</span><span class="arrow right"></span></button><!----></section><!--]--></li></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-database"></i><span class="title">数据库</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-Tools"></i><span class="title">开发工具</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-xitongsheji"></i><span class="title">系统设计</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-distributed-network"></i><span class="title">分布式</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-et-performance"></i><span class="title">高性能</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-CalendarAvailability-1"></i><span class="title">高可用</span><span class="arrow right"></span></button><!----></section><!--]--></li></ul><!--[--><!----><!--]--></aside><!--[--><main class="page" id="main-content"><!----><nav class="breadcrumb disable"></nav><div class="page-title"><h1><!---->线性数据结构 :数组、链表、栈、队列</h1><div class="article-info"><span class="author-info" arialabel="作者🖊" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon author-icon" viewbox="0 0 1024 1024" arialabelledby="author"><title id="author" lang="en">author icon</title><g fill="currentColor"><path d="M649.6 633.6c86.4-48 147.2-144 147.2-249.6 0-160-128-288-288-288s-288 128-288 288c0 108.8 57.6 201.6 147.2 249.6-121.6 48-214.4 153.6-240 288-3.2 9.6 0 19.2 6.4 25.6 3.2 9.6 12.8 12.8 22.4 12.8h704c9.6 0 19.2-3.2 25.6-12.8 6.4-6.4 9.6-16 6.4-25.6-25.6-134.4-121.6-240-243.2-288z"></path></g></svg><span><a class="author-item" href="https://javaguide.cn/" target="_blank" rel="noopener noreferrer">Guide</a></span><span property="author" content="Guide"></span></span><span class="category-info" arialabel="分类🌈" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon category-icon" viewbox="0 0 1024 1024" arialabelledby="category"><title id="category" lang="en">category icon</title><g fill="currentColor"><path d="M148.41 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H148.41c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.311-40.31zM147.556 553.478H429.73c22.263 0 40.311 18.048 40.311 40.31v282.176c0 22.263-18.048 40.312-40.31 40.312H147.555c-22.263 0-40.311-18.049-40.311-40.312V593.79c0-22.263 18.048-40.311 40.31-40.311zM593.927 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H593.927c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.31-40.31zM730.22 920.502H623.926c-40.925 0-74.22-33.388-74.22-74.425V623.992c0-41.038 33.387-74.424 74.425-74.424h222.085c41.038 0 74.424 33.226 74.424 74.067v114.233c0 10.244-8.304 18.548-18.547 18.548s-18.548-8.304-18.548-18.548V623.635c0-20.388-16.746-36.974-37.33-36.974H624.13c-20.585 0-37.331 16.747-37.331 37.33v222.086c0 20.585 16.654 37.331 37.126 37.331H730.22c10.243 0 18.547 8.304 18.547 18.547 0 10.244-8.304 18.547-18.547 18.547z"></path></g></svg><ul class="categories-wrapper"><li class="category clickable" role="navigation">计算机基础</li><meta property="articleSection" content="计算机基础"></ul></span><span arialabel="标签🏷" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon tag-icon" viewbox="0 0 1024 1024" arialabelledby="tag"><title id="tag" lang="en">tag icon</title><g fill="currentColor"><path d="M939.902 458.563L910.17 144.567c-1.507-16.272-14.465-29.13-30.737-30.737L565.438 84.098h-.402c-3.215 0-5.726 1.005-7.634 2.913l-470.39 470.39a10.004 10.004 0 000 14.164l365.423 365.424c1.909 1.908 4.42 2.913 7.132 2.913s5.223-1.005 7.132-2.913l470.39-470.39c2.01-2.11 3.014-5.023 2.813-8.036zm-240.067-72.121c-35.458 0-64.286-28.828-64.286-64.286s28.828-64.285 64.286-64.285 64.286 28.828 64.286 64.285-28.829 64.286-64.286 64.286z"></path></g></svg><ul class="tags-wrapper"><li class="tag clickable" role="navigation">数据结构</li></ul><meta property="keywords" content="数据结构"></span><span class="date-info" arialabel="写作日期📅" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon calendar-icon" viewbox="0 0 1024 1024" arialabelledby="calendar"><title id="calendar" lang="en">calendar icon</title><g fill="currentColor"><path d="M716.4 110.137c0-18.753-14.72-33.473-33.472-33.473-18.753 0-33.473 14.72-33.473 33.473v33.473h66.993v-33.473zm-334.87 0c0-18.753-14.72-33.473-33.473-33.473s-33.52 14.72-33.52 33.473v33.473h66.993v-33.473zm468.81 33.52H716.4v100.465c0 18.753-14.72 33.473-33.472 33.473a33.145 33.145 0 01-33.473-33.473V143.657H381.53v100.465c0 18.753-14.72 33.473-33.473 33.473a33.145 33.145 0 01-33.473-33.473V143.657H180.6A134.314 134.314 0 0046.66 277.595v535.756A134.314 134.314 0 00180.6 947.289h669.74a134.36 134.36 0 00133.94-133.938V277.595a134.314 134.314 0 00-133.94-133.938zm33.473 267.877H147.126a33.145 33.145 0 01-33.473-33.473c0-18.752 14.72-33.473 33.473-33.473h736.687c18.752 0 33.472 14.72 33.472 33.473a33.145 33.145 0 01-33.472 33.473z"></path></g></svg><span>2022年3月3日</span><meta property="datePublished" content="2022-03-03T01:14:56.000Z"></span><!----><span class="words-info" arialabel="字数🔠" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon word-icon" viewbox="0 0 1024 1024" arialabelledby="word"><title id="word" lang="en">word icon</title><g fill="currentColor"><path d="M518.217 432.64V73.143A73.143 73.143 0 01603.43 1.097a512 512 0 01419.474 419.474 73.143 73.143 0 01-72.046 85.212H591.36a73.143 73.143 0 01-73.143-73.143z"></path><path d="M493.714 566.857h340.297a73.143 73.143 0 0173.143 85.577A457.143 457.143 0 11371.566 117.76a73.143 73.143 0 0185.577 73.143v339.383a36.571 36.571 0 0036.571 36.571z"></path></g></svg><span>约 3403 字</span><meta property="wordCount" content="3403"></span></div><hr></div><div class="toc-place-holder"><aside id="toc-list"><div class="toc-header">此页内容</div><div class="toc-wrapper"><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_1-数组" class="router-link-active router-link-exact-active toc-link level2">1. 数组</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-链表" class="router-link-active router-link-exact-active toc-link level2">2. 链表</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-1-链表简介" class="router-link-active router-link-exact-active toc-link level3">2.1. 链表简介</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-2-链表分类" class="router-link-active router-link-exact-active toc-link level3">2.2. 链表分类</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-3-应用场景" class="router-link-active router-link-exact-active toc-link level3">2.3. 应用场景</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_2-4-数组-vs-链表" class="router-link-active router-link-exact-active toc-link level3">2.4. 数组 vs 链表</a></li><!----><!--]--></ul><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-栈" class="router-link-active router-link-exact-active toc-link level2">3. 栈</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-1-栈简介" class="router-link-active router-link-exact-active toc-link level3">3.1. 栈简介</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-2-栈的常见应用常见应用场景" class="router-link-active router-link-exact-active toc-link level3">3.2. 栈的常见应用常见应用场景</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_3-3-栈的实现" class="router-link-active router-link-exact-active toc-link level3">3.3. 栈的实现</a></li><!----><!--]--></ul><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-队列" class="router-link-active router-link-exact-active toc-link level2">4. 队列</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-1-队列简介" class="router-link-active router-link-exact-active toc-link level3">4.1. 队列简介</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-2-队列分类" class="router-link-active router-link-exact-active toc-link level3">4.2. 队列分类</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/linear-data-structure.html#_4-3-常见应用场景" class="router-link-active router-link-exact-active toc-link level3">4.3. 常见应用场景</a></li><!----><!--]--></ul><!--]--></ul></div></aside></div><!----><div class="theme-hope-content"><!--[--><h1 id="线性数据结构-数组、链表、栈、队列" tabindex="-1"><a class="header-anchor" href="#线性数据结构-数组、链表、栈、队列" aria-hidden="true">#</a> 线性数据结构 :数组、链表、栈、队列</h1><blockquote><p>开头还是求点赞，求转发！原创优质公众号，希望大家能让更多人看到我们的文章。</p><p>图片都是我们手绘的，可以说非常用心了！</p></blockquote><h2 id="_1-数组" tabindex="-1"><a class="header-anchor" href="#_1-数组" aria-hidden="true">#</a> 1. 数组</h2><p><strong>数组（Array）</strong> 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。</p><p>我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。</p><p>数组的特点是：<strong>提供随机访问</strong> 并且容量有限。</p><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code>假如数组的长度为 n。
访问：<span class="token class-name">O</span>（<span class="token number">1</span>）<span class="token comment">//访问特定位置的元素</span>
插入：<span class="token class-name">O</span>（n ）<span class="token comment">//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时</span>
删除：<span class="token class-name">O</span>（n）<span class="token comment">//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/数组.png" alt="数组" loading="lazy"></p><h2 id="_2-链表" tabindex="-1"><a class="header-anchor" href="#_2-链表" aria-hidden="true">#</a> 2. 链表</h2><h3 id="_2-1-链表简介" tabindex="-1"><a class="header-anchor" href="#_2-1-链表简介" aria-hidden="true">#</a> 2.1. 链表简介</h3><p><strong>链表（LinkedList）</strong> 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。</p><p>链表的插入和删除操作的复杂度为 O(1) ，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。</p><p>使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。</p><h3 id="_2-2-链表分类" tabindex="-1"><a class="header-anchor" href="#_2-2-链表分类" aria-hidden="true">#</a> 2.2. 链表分类</h3><p><strong>常见链表分类：</strong></p><ol><li>单链表</li><li>双向链表</li><li>循环链表</li><li>双向循环链表</li></ol><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code>假如链表中有n个元素。
访问：<span class="token class-name">O</span>（n）<span class="token comment">//访问特定位置的元素</span>
插入删除：<span class="token class-name">O</span>（<span class="token number">1</span>）<span class="token comment">//必须要要知道插入元素的位置</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h4 id="_2-2-1-单链表" tabindex="-1"><a class="header-anchor" href="#_2-2-1-单链表" aria-hidden="true">#</a> 2.2.1. 单链表</h4><p><strong>单链表</strong> 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/单链表2.png" alt="单链表" loading="lazy"></p><h4 id="_2-2-2-循环链表" tabindex="-1"><a class="header-anchor" href="#_2-2-2-循环链表" aria-hidden="true">#</a> 2.2.2. 循环链表</h4><p><strong>循环链表</strong> 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/循环链表2.png" alt="循环链表" loading="lazy"></p><h4 id="_2-2-3-双向链表" tabindex="-1"><a class="header-anchor" href="#_2-2-3-双向链表" aria-hidden="true">#</a> 2.2.3. 双向链表</h4><p><strong>双向链表</strong> 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/双向链表.png" alt="双向链表" loading="lazy"></p><h4 id="_2-2-4-双向循环链表" tabindex="-1"><a class="header-anchor" href="#_2-2-4-双向循环链表" aria-hidden="true">#</a> 2.2.4. 双向循环链表</h4><p><strong>双向循环链表</strong> 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/双向循环链表.png" alt="双向循环链表" loading="lazy"></p><h3 id="_2-3-应用场景" tabindex="-1"><a class="header-anchor" href="#_2-3-应用场景" aria-hidden="true">#</a> 2.3. 应用场景</h3><ul><li>如果需要支持随机访问的话，链表没办法做到。</li><li>如果需要存储的数据元素的个数不确定，并且需要经常添加和删除数据的话，使用链表比较合适。</li><li>如果需要存储的数据元素的个数确定，并且不需要经常添加和删除数据的话，使用数组比较合适。</li></ul><h3 id="_2-4-数组-vs-链表" tabindex="-1"><a class="header-anchor" href="#_2-4-数组-vs-链表" aria-hidden="true">#</a> 2.4. 数组 vs 链表</h3><ul><li>数组支持随机访问，而链表不支持。</li><li>数组使用的是连续内存空间对 CPU 的缓存机制友好，链表则相反。</li><li>数组的大小固定，而链表则天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比较耗时的！</li></ul><h2 id="_3-栈" tabindex="-1"><a class="header-anchor" href="#_3-栈" aria-hidden="true">#</a> 3. 栈</h2><h3 id="_3-1-栈简介" tabindex="-1"><a class="header-anchor" href="#_3-1-栈简介" aria-hidden="true">#</a> 3.1. 栈简介</h3><p><strong>栈</strong> (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 <strong>后进先出（LIFO, Last In First Out）</strong> 的原理运作。<strong>在栈中，push 和 pop 的操作都发生在栈顶。</strong></p><p>栈常用一维数组或链表来实现，用数组实现的栈叫作 <strong>顺序栈</strong> ，用链表实现的栈叫作 <strong>链式栈</strong> 。</p><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code>假设堆栈中有n个元素。
访问：<span class="token class-name">O</span>（n）<span class="token comment">//最坏情况</span>
插入删除：<span class="token class-name">O</span>（<span class="token number">1</span>）<span class="token comment">//顶端插入和删除元素</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/栈.png" alt="栈" loading="lazy"></p><h3 id="_3-2-栈的常见应用常见应用场景" tabindex="-1"><a class="header-anchor" href="#_3-2-栈的常见应用常见应用场景" aria-hidden="true">#</a> 3.2. 栈的常见应用常见应用场景</h3><p>当我们我们要处理的数据只涉及在一端插入和删除数据，并且满足 <strong>后进先出（LIFO, Last In First Out）</strong> 的特性时，我们就可以使用栈这个数据结构。</p><h4 id="_3-2-1-实现浏览器的回退和前进功能" tabindex="-1"><a class="header-anchor" href="#_3-2-1-实现浏览器的回退和前进功能" aria-hidden="true">#</a> 3.2.1. 实现浏览器的回退和前进功能</h4><p>我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。示例图如下:</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/栈实现浏览器倒退和前进.png" alt="栈实现浏览器倒退和前进" loading="lazy"></p><h4 id="_3-2-2-检查符号是否成对出现" tabindex="-1"><a class="header-anchor" href="#_3-2-2-检查符号是否成对出现" aria-hidden="true">#</a> 3.2.2. 检查符号是否成对出现</h4><blockquote><p>给定一个只包括 <code>&#39;(&#39;</code>，<code>&#39;)&#39;</code>，<code>&#39;{&#39;</code>，<code>&#39;}&#39;</code>，<code>&#39;[&#39;</code>，<code>&#39;]&#39;</code> 的字符串，判断该字符串是否有效。</p><p>有效字符串需满足：</p><ol><li>左括号必须用相同类型的右括号闭合。</li><li>左括号必须以正确的顺序闭合。</li></ol><p>比如 &quot;()&quot;、&quot;()[]{}&quot;、&quot;{[]}&quot; 都是有效字符串，而 &quot;(]&quot; 、&quot;([)]&quot; 则不是。</p></blockquote><p>这个问题实际是 Leetcode 的一道题目，我们可以利用栈 <code>Stack</code> 来解决这个问题。</p><ol><li>首先我们将括号间的对应规则存放在 <code>Map</code> 中，这一点应该毋容置疑；</li><li>创建一个栈。遍历字符串，如果字符是左括号就直接加入<code>stack</code>中，否则将<code>stack</code> 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果<code>stack</code>为空，返回 <code>true</code>。</li></ol><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isValid</span><span class="token punctuation">(</span><span class="token class-name">String</span> s<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// 括号之间的对应规则</span>
    <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Character</span><span class="token punctuation">,</span> <span class="token class-name">Character</span><span class="token punctuation">&gt;</span></span> mappings <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Character</span><span class="token punctuation">,</span> <span class="token class-name">Character</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    mappings<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token char">&#39;)&#39;</span><span class="token punctuation">,</span> <span class="token char">&#39;(&#39;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    mappings<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token char">&#39;}&#39;</span><span class="token punctuation">,</span> <span class="token char">&#39;{&#39;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    mappings<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token char">&#39;]&#39;</span><span class="token punctuation">,</span> <span class="token char">&#39;[&#39;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">Stack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Character</span><span class="token punctuation">&gt;</span></span> stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Stack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Character</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">char</span><span class="token punctuation">[</span><span class="token punctuation">]</span> chars <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">toCharArray</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> chars<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>mappings<span class="token punctuation">.</span><span class="token function">containsKey</span><span class="token punctuation">(</span>chars<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">char</span> topElement <span class="token operator">=</span> stack<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token char">&#39;#&#39;</span> <span class="token operator">:</span> stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>topElement <span class="token operator">!=</span> mappings<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>chars<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>chars<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> stack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><h4 id="_3-2-3-反转字符串" tabindex="-1"><a class="header-anchor" href="#_3-2-3-反转字符串" aria-hidden="true">#</a> 3.2.3. 反转字符串</h4><p>将字符串中的每个字符先入栈再出栈就可以了。</p><h4 id="_3-2-4-维护函数调用" tabindex="-1"><a class="header-anchor" href="#_3-2-4-维护函数调用" aria-hidden="true">#</a> 3.2.4. 维护函数调用</h4><p>最后一个被调用的函数必须先完成执行，符合栈的 <strong>后进先出（LIFO, Last In First Out）</strong> 特性。</p><h3 id="_3-3-栈的实现" tabindex="-1"><a class="header-anchor" href="#_3-3-栈的实现" aria-hidden="true">#</a> 3.3. 栈的实现</h3><p>栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。</p><p>下面我们使用数组来实现一个栈，并且这个栈具有<code>push()</code>、<code>pop()</code>（返回栈顶元素并出栈）、<code>peek()</code> （返回栈顶元素不出栈）、<code>isEmpty()</code>、<code>size()</code>这些基本的方法。</p><blockquote><p>提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用<code>Arrays.copyOf()</code>进行扩容；</p></blockquote><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MyStack</span> <span class="token punctuation">{</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> storage<span class="token punctuation">;</span><span class="token comment">//存放栈中元素的数组</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> capacity<span class="token punctuation">;</span><span class="token comment">//栈的容量</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> count<span class="token punctuation">;</span><span class="token comment">//栈中元素数量</span>
    <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> GROW_FACTOR <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span>

    <span class="token comment">//不带初始容量的构造方法。默认容量为8</span>
    <span class="token keyword">public</span> <span class="token class-name">MyStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>capacity <span class="token operator">=</span> <span class="token number">8</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>storage<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token number">8</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//带初始容量的构造方法</span>
    <span class="token keyword">public</span> <span class="token class-name">MyStack</span><span class="token punctuation">(</span><span class="token keyword">int</span> initialCapacity<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>initialCapacity <span class="token operator">&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Capacity too small.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span>capacity <span class="token operator">=</span> initialCapacity<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>storage <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>initialCapacity<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//入栈</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>count <span class="token operator">==</span> capacity<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token function">ensureCapacity</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        storage<span class="token punctuation">[</span>count<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> value<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//确保容量大小</span>
    <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">ensureCapacity</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> newCapacity <span class="token operator">=</span> capacity <span class="token operator">*</span> GROW_FACTOR<span class="token punctuation">;</span>
        storage <span class="token operator">=</span> <span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">copyOf</span><span class="token punctuation">(</span>storage<span class="token punctuation">,</span> newCapacity<span class="token punctuation">)</span><span class="token punctuation">;</span>
        capacity <span class="token operator">=</span> newCapacity<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//返回栈顶元素并出栈</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>count <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Stack is empty.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        count<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> storage<span class="token punctuation">[</span>count<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//返回栈顶元素不出栈</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> <span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>count <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Stack is empty.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> storage<span class="token punctuation">[</span>count<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//判断栈是否为空</span>
    <span class="token keyword">private</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> count <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//返回栈中元素的个数</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> count<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br></div></div><p>验证</p><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code><span class="token class-name">MyStack</span> myStack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyStack</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">7</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
myStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">8</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myStack<span class="token punctuation">.</span><span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//8</span>
<span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myStack<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//8</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">8</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myStack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myStack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//true</span>
myStack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//报错：java.lang.IllegalArgumentException: Stack is empty.</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><h2 id="_4-队列" tabindex="-1"><a class="header-anchor" href="#_4-队列" aria-hidden="true">#</a> 4. 队列</h2><h3 id="_4-1-队列简介" tabindex="-1"><a class="header-anchor" href="#_4-1-队列简介" aria-hidden="true">#</a> 4.1. 队列简介</h3><p><strong>队列</strong> 是 <strong>先进先出( FIFO，First In, First Out)</strong> 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 <strong>顺序队列</strong> ，用链表实现的队列叫作 <strong>链式队列</strong> 。<strong>队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue</strong></p><p>队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。</p><div class="language-java ext-java line-numbers-mode"><pre class="language-java"><code>假设队列中有n个元素。
访问：<span class="token class-name">O</span>（n）<span class="token comment">//最坏情况</span>
插入删除：<span class="token class-name">O</span>（<span class="token number">1</span>）<span class="token comment">//后端插入前端删除元素</span>
</code></pre><div class="line-numbers" aria-hidden="true"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/队列.png" alt="队列" loading="lazy"></p><h3 id="_4-2-队列分类" tabindex="-1"><a class="header-anchor" href="#_4-2-队列分类" aria-hidden="true">#</a> 4.2. 队列分类</h3><h4 id="_4-2-1-单队列" tabindex="-1"><a class="header-anchor" href="#_4-2-1-单队列" aria-hidden="true">#</a> 4.2.1. 单队列</h4><p>单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 <strong>顺序队列（数组实现）</strong> 和 <strong>链式队列（链表实现）</strong>。</p><p><strong>顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。</strong></p><p>假设下图是一个顺序队列，我们将前两个元素 1,2 出队，并入队两个元素 7,8。当进行入队、出队操作的时候，front 和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 <strong>”假溢出“</strong> 。除了假溢出问题之外，如下图所示，当添加元素 8 的时候，rear 指针移动到数组之外（越界）。</p><blockquote><p>为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear 指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From 《大话数据结构》</p></blockquote><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/顺序队列假溢出1.png" alt="顺序队列假溢出" loading="lazy"></p><h4 id="_4-2-2-循环队列" tabindex="-1"><a class="header-anchor" href="#_4-2-2-循环队列" aria-hidden="true">#</a> 4.2.2. 循环队列</h4><p>循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。</p><p>还是用上面的图，我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候， rear 向后移动。</p><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/循环队列.png" alt="循环队列" loading="lazy"></p><p>顺序队列中，我们说 <code>front==rear</code> 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：</p><ol><li>可以设置一个标志变量 <code>flag</code>,当 <code>front==rear</code> 并且 <code>flag=0</code> 的时候队列为空，当<code>front==rear</code> 并且 <code>flag=1</code> 的时候队列为满。</li><li>队列为空的时候就是 <code>front==rear</code> ，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，如下图所示，那么现在判断队列是否为满的条件就是： <code>(rear+1) % QueueSize= front</code> 。</li></ol><p><img src="https://my-blog-to-use.oss-cn-beijing.aliyuncs.com/2019-6/循环队列-堆满.png" alt="循环队列-队满" loading="lazy"></p><h3 id="_4-3-常见应用场景" tabindex="-1"><a class="header-anchor" href="#_4-3-常见应用场景" aria-hidden="true">#</a> 4.3. 常见应用场景</h3><p>当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。</p><ul><li><strong>阻塞队列：</strong> 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。</li><li><strong>线程池中的请求/任务队列：</strong> 线程池中没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？答案是将这些请求放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如 ：<code>FixedThreadPool</code> 使用无界队列 <code>LinkedBlockingQueue</code>。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出<code>java.util.concurrent.RejectedExecutionException</code> 异常。</li><li>Linux 内核进程队列（按优先级排队）</li><li>现实生活中的派对，播放器上的播放列表;</li><li>消息队列</li><li>等等......</li></ul><!--]--></div><!----><footer class="page-meta"><div class="meta-item edit-link"><a href="https://github.com/Snailclimb/JavaGuide/edit/main/docs/cs-basics/data-structure/linear-data-structure.md" rel="noopener noreferrer" target="_blank" arialabel="编辑此页" class="nav-link label"><!--[--><svg xmlns="http://www.w3.org/2000/svg" class="icon edit-icon" viewbox="0 0 1024 1024" arialabelledby="edit"><title id="edit" lang="en">edit icon</title><g fill="currentColor"><path d="M430.818 653.65a60.46 60.46 0 0 1-50.96-93.281l71.69-114.012 7.773-10.365L816.038 80.138A60.46 60.46 0 0 1 859.225 62a60.46 60.46 0 0 1 43.186 18.138l43.186 43.186a60.46 60.46 0 0 1 0 86.373L588.879 565.55l-8.637 8.637-117.466 68.234a60.46 60.46 0 0 1-31.958 11.229z"></path><path d="M728.802 962H252.891A190.883 190.883 0 0 1 62.008 771.98V296.934a190.883 190.883 0 0 1 190.883-192.61h267.754a60.46 60.46 0 0 1 0 120.92H252.891a69.962 69.962 0 0 0-69.098 69.099V771.98a69.962 69.962 0 0 0 69.098 69.098h475.911A69.962 69.962 0 0 0 797.9 771.98V503.363a60.46 60.46 0 1 1 120.922 0V771.98A190.883 190.883 0 0 1 728.802 962z"></path></g></svg><!--]-->编辑此页<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="meta-item update-time"><span class="label">上次编辑于: </span><span class="info">2022/3/3 09:14:56</span></div><div class="meta-item contributors"><span class="label">贡献者: </span><!--[--><!--[--><span class="contributor" title="email: koushuangbwcx@163.com">guide</span><!--]--><!--]--></div></footer><nav class="page-nav"><!----><a href="/cs-basics/data-structure/graph.html" class="nav-link next" arialabel="图"><div class="hint">下一页<span class="arrow right"></span></div><div class="link">图<!----></div></a></nav><!----><!----></main><!--]--><footer class="footer-wrapper"><div class="footer"><a href="https://beian.miit.gov.cn/" target="_blank">鄂ICP备2020015769号-1</a></div><div class="copyright">Copyright © 2022 Guide</div></footer></div><!--]--><!----><!--]--></div>
    <script type="module" src="/assets/app.93341f6d.js" defer></script>
  </body>
</html>
